#include <iostream>
#include <vector>

using namespace std;
typedef pair<int, int> PII;
const int N = 1e4 + 10;
const int INF = 2147483647;

int n, m, s;
vector<PII> edges[N];
bool st[N];
int dist[N];

void bf(int s)
{
    for(int i = 0; i <= n; i++) dist[i] = INF;
    dist[s] = 0;
    for(int i = 1; i <= n - 1; i++)
    {
        bool flag = true;
        for(int u = 1; u <= n; u++)
        {
            if(dist[u] == INF) continue;
            for(auto & t : edges[u])
            {
                int v = t.first, w = t.second;
                if(dist[u] + w < dist[v])
                {
                    flag = false;
                    dist[v] = dist[u] + w;
                }
            }
        }
        if(flag) break;
    }
    for(int i = 1; i <= n; i++) cout << dist[i] << " ";
}

int main()
{
    cin >> n >> m >> s;
    for(int i = 1; i <= m; i++)
    {
        int u, v, w; cin >> u >> v >> w;
        edges[u].push_back({v, w});
    }
    bf(s);
}